package main

import "fmt"

func format(board [][]byte) {
	for i := byte(0); i < 9; i++ {
		for j := byte(0); j < 9; j++ {
			if board[i][j] == '.' {
				board[i][j] = 0
			} else {
				board[i][j] -= '0'
			}
		}
	}
}

func backFormat(board [][]byte) {
	for i := byte(0); i < 9; i++ {
		for j := byte(0); j < 9; j++ {
			board[i][j] += '0'
		}
	}
}

func getEmptyPoints(board [][]byte) [][2]byte {
	points := [][2]byte{}
	for i := byte(0); i < 9; i++ {
		for j := byte(0); j < 9; j++ {
			if board[i][j] == 0 {
				point := [2]byte{i, j}
				points = append(points, point)
			}
		}
	}
	return points
}

func getChoices(board [][]byte, row byte, col byte) []byte {
	spaces := make([]bool, 9+1)

	for j := 0; j < 9; j++ {
		spaces[board[row][j]] = true
	}
	for i := 0; i < 9; i++ {
		spaces[board[i][col]] = true
	}

	for i := row / 3 * 3; i < row/3*3+3; i++ {
		for j := col / 3 * 3; j < col/3*3+3; j++ {
			spaces[board[i][j]] = true
		}
	}

	choices := []byte{}
	for i := byte(1); i <= 9; i++ {
		if spaces[i] == false {
			choices = append(choices, i)
		}
	}
	return choices

}

func solveSudoku(board [][]byte) {
	format(board)
	points := getEmptyPoints(board)
	n := len(points)
	allChoices := make([][]byte, n)
	hasChosens := make([]bool, n)
	for i := 0; i < n; {
		row, col := points[i][0], points[i][1]
		choices := allChoices[i]
		if hasChosens[i] == false {
			choices = getChoices(board, row, col)
			hasChosens[i] = true
		}
		if len(choices) == 0 {
			hasChosens[i] = false
			board[row][col] = 0
			if i > 0 {
				i--
				continue
			} else {
				fmt.Println(i)
				fmt.Println(hasChosens[i])
				fmt.Println(points[i])
				fmt.Println("Error")
				return
			}

		}
		board[row][col] = choices[0]
		allChoices[i] = choices[1:]
		i++
	}

	backFormat(board)

}

//*/
func main() {
	board := [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}
	//format(board)
	//fmt.Println(getEmptyPoints(board))
	//fmt.Println(getChoices(board, 1, 7))
	//fmt.Println(board)
	solveSudoku(board)
	//fmt.Println(board)
	//backFormat(board)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			fmt.Printf("%c ", board[i][j])
		}
		fmt.Println()
	}
}
